1. 12.2 决策树分类原理

1.1. 学习目标

知道如何求解信息熵
知道信息增益的求解过程
知道信息增益率的求解过程
知道基尼系数的求解过程
知道信息增益、信息增益率和基尼系数三者之间的区别、联系

1.2. 1 熵

1.2.1. 1.1 概念

物理学上，熵 Entropy 是“混乱”程度的量度。

系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

1948年香农提出了信息熵（Entropy）的概念。

信息理论：

1、从信息的完整性上进行的描述:

当系统的有序状态一致时，数据越集中的地方熵值越小，数据越分散的地方熵值越大。

2、从信息的有序性上进行的描述:

当数据量一致时，系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

"信息熵" (information entropy)是度量样本集合纯度最常用的一种指标。

假定当前样本集合 D 中第 k 类样本所占的比例为 pk (k = 1, 2,. . . , |y|) ， $p_k=\frac{C^k}{D}$

其中：D为样本的所有数量，Ck 为第k类样本的数量。

则 D的信息熵定义为(（log是以2为底，lg是以10为底）:

其中：Ent(D) 的值越小，则 D 的纯度越高.

1.2.2. 1.2 案例

课堂案例：
假设我们没有看世界杯的比赛，但是想知道哪支球队会是冠军，
我们只能猜测某支球队是或不是冠军，然后观众用对或不对来回答，
我们想要猜测次数尽可能少，你会用什么方法？

答案：
二分法：
假如有 16 支球队，分别编号，先问是否在 1-8 之间，如果是就继续问是否在 1-4 之间，
以此类推，直到最后判断出冠军球队是哪支。
如果球队数量是 16，我们需要问 4 次来得到最后的答案。那么世界冠军这条消息的信息熵就是 4。

那么信息熵等于4，是如何进行计算的呢？
Ent(D) = -（p1 * logp1 + p2 * logp2 + ... + p16 * logp16），
其中 p1, ..., p16 分别是这 16 支球队夺冠的概率。
当每支球队夺冠概率相等都是 1/16 的时：Ent(D) = -（16 * 1/16 * log1/16） = 4
每个事件概率相同时，熵最大，这件事越不确定。
随堂练习：
篮球比赛里，有4个球队 {A,B,C,D} ，获胜概率分别为{1/2, 1/4, 1/8, 1/8}
求Ent(D)

答案：

1.3. 2 划分依据一 -- 信息增益

1.3.1. 2.1 概念

信息增益：以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。

信息增益 = entroy(前) - entroy(后)

注：信息增益表示得知特征X的信息而使得类Y的信息熵减少的程度

定义与公式

假定离散属性a有 V 个可能的取值:

假设离散属性性别有2（男，女）个可能的取值

若使用a来对样本集 D 进行划分，则会产生 V 个分支结点,

其中第v个分支结点包含了 D 中所有在属性a上取值为av的样本，记为Dv.

我们可根据前面给出的信息熵公式计算出Dv的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重。

即样本数越多的分支结点的影响越大，于是可计算出用属性a对样本集 D 进行划分所获得的"信息增益" (information gain)

其中：

特征a对训练数据集D的信息增益Gain(D,a),定义为集合D的信息熵Ent(D)与给定特征a条件下D的信息条件Ent(D|a)之差，即公式为：

公式的详细解释：

信息熵的计算：

条件熵的计算：

其中：

Dv表示a属性中第v个分支节点包含的样本数

Ckv表示a属性中第v个分支节点包含的样本数中，第k个类别下包含的样本数

一般而言，信息增益越大，则意味着使用属性 a 来进行划分所获得的"纯度提升"越大。因此，我们可用信息增益来进行决策树的划分属性选择，著名的 ID3 决策树学习算法 [Quinlan， 1986] 就是以信息增益为准则来选择划分属性。

其中，ID3 名字中的 ID 是 Iterative Dichotomiser (迭代二分器)的简称

1.3.2. 2.2 案例

如下图，第一列为论坛号码，第二列为性别，第三列为活跃度，最后一列用户是否流失。

我们要解决一个问题：性别和活跃度两个特征，哪个对用户流失影响更大？

通过计算信息增益可以解决这个问题，统计上右表信息

其中Positive为正样本（已流失），Negative为负样本（未流失），下面的数值为不同划分下对应的人数。

可得到三个熵：

a.计算类别信息熵

整体熵：

b.计算性别属性的信息熵(a="性别")

c.计算性别的信息增益(a="性别")

b.计算活跃度属性的信息熵(a="活跃度")

c.计算活跃度的信息增益(a="活跃度")

活跃度的信息增益比性别的信息增益大，也就是说，活跃度对用户流失的影响比性别大。在做特征选择或者数据分析的时候，我们应该重点考察活跃度这个指标。

1.4. 3 划分依据二 -- 信息增益率

1.4.1. 3.1 概念

在上面的介绍中，我们有意忽略了"编号"这一列.若把"编号"也作为一个候选划分属性，则根据信息增益公式可计算出它的信息增益为 0.9182，远大于其他候选划分属性。

计算每个属性的信息熵过程中,我们发现,该属性的值为0, 也就是其信息增益为0.9182. 但是很明显这么分类,最后出现的结果不具有泛化效果.无法对新样本进行有效预测.

实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法 [Quinlan， 1993J 不直接使用信息增益，而是使用"增益率" (gain ratio) 来选择最优划分属性.

增益率：增益率是用前面的信息增益Gain(D, a)和属性a对应的"固有值"(intrinsic value) [Quinlan , 1993J的比值来共同定义的。

属性 a 的可能取值数目越多(即 V 越大)，则 IV(a) 的值通常会越大.

1.4.2. 3.2 案例

3.2.1 案例一

a.计算类别信息熵

b.计算性别属性的信息熵(性别、活跃度)

c.计算活跃度的信息增益(性别、活跃度)

d.计算属性分裂信息度量

用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息，我们把这些信息称为属性的内在信息（instrisic information）。信息增益率用信息增益/内在信息，会导致属性的重要性随着内在信息的增大而减小（也就是说，如果这个属性本身不确定性就很大，那我就越不倾向于选取它），这样算是对单纯用信息增益有所补偿。

e.计算信息增益率

活跃度的信息增益率更高一些，所以在构建决策树的时候，优先选择

通过这种方式，在选取节点的过程中，我们可以降低取值较多的属性的选取偏好。

3.2.2 案例二

如下图，第一列为天气，第二列为温度，第三列为湿度，第四列为风速，最后一列该活动是否进行。

我们要解决：根据下面表格数据，判断在对应天气下，活动是否会进行？

该数据集有四个属性，属性集合A={ 天气，温度，湿度，风速}，类别标签有两个，类别集合L={进行，取消}。

a.计算类别信息熵

类别信息熵表示的是所有样本中各种类别出现的不确定性之和。根据熵的概念，熵越大，不确定性就越大，把事情搞清楚所需要的信息量就越多。 $Ent(D)=-\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940$ b.计算每个属性的信息熵

每个属性的信息熵相当于一种条件熵。他表示的是在某种属性的条件下，各种类别出现的不确定性之和。属性的信息熵越大，表示这个属性中拥有的样本类别越不“纯”。

c.计算信息增益

信息增益的 = 熵 - 条件熵，在这里就是类别信息熵 - 属性信息熵，它表示的是信息不确定性减少的程度。如果一个属性的信息增益越大，就表示用这个属性进行样本划分可以更好的减少划分后样本的不确定性，当然，选择该属性就可以更快更好地完成我们的分类目标。

信息增益就是ID3算法的特征选择指标。

假设我们把上面表格1的数据前面添加一列为"编号",取值(1--14). 若把"编号"也作为一个候选划分属性,则根据前面步骤: 计算每个属性的信息熵过程中,我们发现,该属性的值为0, 也就是其信息增益为0.940. 但是很明显这么分类,最后出现的结果不具有泛化效果.此时根据信息增益就无法选择出有效分类特征。所以，C4.5选择使用信息增益率对ID3进行改进。

d.计算属性分裂信息度量

e.计算信息增益率

天气的信息增益率最高，选择天气为分裂属性。发现分裂了之后，天气是“阴”的条件下，类别是”纯“的，所以把它定义为叶子节点，选择不“纯”的结点继续分裂。

在子结点当中重复过程1~5，直到所有的叶子结点足够"纯"。

现在我们来总结一下C4.5的算法流程

while(当前节点"不纯")：
    1.计算当前节点的类别熵(以类别取值计算)
    2.计算当前阶段的属性熵(按照属性取值吓得类别取值计算)
    3.计算信息增益
    4.计算各个属性的分裂信息度量
    5.计算各个属性的信息增益率
end while
当前阶段设置为叶子节点

1.4.3. 3.3 为什么使用C4.5要好

1.用信息增益率来选择属性

克服了用信息增益来选择属性时偏向选择值多的属性的不足。

2.采用了一种后剪枝方法

避免树的高度无节制的增长，避免过度拟合数据

3.对于缺失值的处理

在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈x，c(x)〉是样本集S中的一个训练实例，但是其属性A的值A(x)未知。

处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；

另外一种更复杂的策略是为A的每个可能值赋予一个概率。

例如，给定一个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。

C4.5就是使用这种方法处理缺少的属性值。

1.5. 4 划分依据三 -- 基尼值和基尼指数

1.5.1. 4.1 概念

CART 决策树 [Breiman et al., 1984] 使用"基尼指数" (Gini index)来选择划分属性.

CART 是Classification and Regression Tree的简称，这是一种著名的决策树学习算法,分类和回归任务都可用

基尼值Gini（D）：从数据集D中随机抽取两个样本，其类别标记不一致的概率。故，Gini（D）值越小，数据集D的纯度越高。

数据集 D 的纯度可用基尼值来度量:

$> p_k=\frac{C^k}{D} >$

其中：D为样本的所有数量，Ck为第k类样本的数量。

基尼指数Gini_index（D）：一般，选择使划分后基尼系数最小的属性作为最优化分属性。

1.5.2. 4.2 案例

请根据下图列表，按照基尼指数的划分依据，做出决策树。

序号	是否有房	婚姻状况	年收入	是否拖欠贷款
1	yes	single	125k	no
2	no	married	100k	no
3	no	single	70k	no
4	yes	married	120k	no
5	no	divorced	95k	yes
6	no	married	60k	no
7	yes	divorced	220k	no
8	no	single	85k	yes
9	no	married	75k	no
10	No	Single	90k	Yes

1，对数据集非序列标号属性{是否有房，婚姻状况，年收入}分别计算它们的Gini指数，取Gini指数最小的属性作为决策树的根节点属性。

第一次大循环

2，根节点的Gini值为：

3，当根据是否有房来进行划分时，Gini指数计算过程为：

4，若按婚姻状况属性来划分，属性婚姻状况有三个可能的取值{married，single，divorced}，分别计算划分后的Gini系数增益。

{married} | {single,divorced}

{single} | {married,divorced}

{divorced} | {single,married}

对比计算结果，根据婚姻状况属性来划分根节点时取Gini指数最小的分组作为划分结果，即:

{married} | {single,divorced}

5，同理可得年收入Gini：

对于年收入属性为数值型属性，首先需要对数据按升序排序，然后从小到大依次用相邻值的中间值作为分隔将样本划分为两组。例如当面对年收入为60和70这两个值时，我们算得其中间值为65。以中间值65作为分割点求出Gini指数。

根据计算知道，三个属性划分根节点的指数最小的有两个：年收入属性和婚姻状况，他们的指数都为0.3。此时，选取首先出现的属性【married】作为第一次划分。

第二次大循环

6，接下来，采用同样的方法，分别计算剩下属性，其中根节点的Gini系数为（此时是否拖欠贷款的各有3个records）

7，对于是否有房属性，可得：

8，对于年收入属性则有：

经过如上流程，构建的决策树，如下图：

现在我们来总结一下CART的算法流程

while(当前节点"不纯")：
    1.遍历每个变量的每一种分割方式，找到最好的分割点
    2.分割成两个节点N1和N2
end while
每个节点足够“纯”为止

1.6. 5 小结

1.6.1. 5.1 常见决策树的启发函数比较

名称	提出时间	分支方式	备注
ID3	1975	信息增益	ID3只能对离散属性的数据集构成决策树
C4.5	1993	信息增益率	优化后解决了ID3分支过程中总喜欢偏向选择值较多的属性
CART	1984	Gini系数	可以进行分类和回归，可以处理离散属性，也可以处理连续属性

5.1.1 ID3 算法

存在的缺点
- (1) ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息.
- (2) ID3算法只能对描述属性为离散型属性的数据集构造决策树。

5.1.2 C4.5算法

做出的改进(为什么使用C4.5要好)
- (1) 用信息增益率来选择属性
- (2) 可以处理连续数值型属性
- (3)采用了一种后剪枝方法
- (4)对于缺失值的处理
C4.5算法的优缺点
- 优点：
  - 产生的分类规则易于理解，准确率较高。
- 缺点：
  - 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。
  - 此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

5.1.3 CART算法

CART算法相比C4.5算法的分类方法，采用了简化的二叉树模型，同时特征选择采用了近似的基尼系数来简化计算。
C4.5不一定是二叉树，但CART一定是二叉树。

5.1.4 多变量决策树

同时，无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1，这里不多介绍。
如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

1.6.2. 5.2 决策树变量的两种类型

数字型（Numeric）：变量类型是整数或浮点数，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。
名称型（Nominal）：类似编程语言中的枚举类型，变量只能从有限的选项中选取，比如前面例子中的“婚姻情况”，只能是“单身”，“已婚”或“离婚”，使用“=”来分割。

1.6.3. 5.3 如何评估分割点的好坏

如果一个分割点可以将当前的所有节点分为两类，使得每一类都很“纯”，也就是同一类的记录较多，那么就是一个好分割点。
比如上面的例子，“拥有房产”，可以将记录分成了两类，“是”的节点全部都可以偿还债务，非常“纯”；“否”的节点，可以偿还贷款和无法偿还贷款的人都有，不是很“纯”，但是两个节点加起来的纯度之和与原始节点的纯度之差最大，所以按照这种方法分割。
构建决策树采用贪心算法，只考虑当前纯度差最大的情况作为分割点。

12.2 决策树分类原理